﻿// 0815train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <limits>

using namespace std;

/*
服务器连接方式包括直接相连，间接连接。A 和 B 直接连接，B 和 C 直接连接，则 A 和 C 间接连接。
直接连接和间接连接都可以发送广播。
给出一个大小为 N*N 的二维矩阵matrix，代表 N 个服务器。
matrix[i][j] = 1，则代表 i 和 j 直接连接；matrix[i][j] = 0 时，代表 i 和 j 不直接连接。
matrix[i][j]==1，即自己和自已直接连接。
计算初始需要给几台服务器广播，才可以使每个服务器都收到广播。
输入
输入为 N 行，每行有 N 个数字，为 0 成 1，由空格分隔，构成 N*N 的二维矩阵matrix，N 的范围为 1 <= N <= 40。
输出
输出一个数字，为需要广播的服务器的数量。

输入
1 0 0
0 1 0
0 0 1
输出
3

示例 2
输入
1 1
1 1
输出
1

 */

void solve01(vector<vector<int>>&grid)
{
    //checked_vec bfs_queue
    //for循环, !is_visited, bfs_queue.push
    //!bfs_queue.empty

    int grid_size = grid.size();
    vector<bool>checked_vec(grid_size, false);

    queue<int>bfs_queue;

    int result = 0;
    for (int node=0; node<grid_size; node++)
    {
        bool is_visited = checked_vec[node];
        if (!is_visited)
        {
            bfs_queue.push(node);
            //标记已访问
            checked_vec[node] = true;
            while (!bfs_queue.empty())
            {
                int top_node = bfs_queue.front();
                bfs_queue.pop();

                vector<int>curr_vec = grid[top_node];
                for (int next_node=0; next_node<grid_size;next_node++)
                {
                    //3重条件 1不相等 2可到达 3未访问
                    bool is_next_available = curr_vec[next_node] == 1;
                    bool is_next_visited = checked_vec[next_node];
                    if (next_node!= top_node && is_next_available && !is_next_visited)
                    {
                        bfs_queue.push(next_node);
                        //标记已访问
                        checked_vec[next_node] = true;
                    }
                }

                //while (!bfs_queue.empty())------
            }
            result += 1;
        }
        //for------
    }

    cout << result;
    //solve01------
}


/*
 现有一个机器人，可放置于 M × N 的网格 grid 中任意位置，每个网格包含一个非负整数编号。
 当相邻网格的数字编号差值的绝对值小于等于 1 时，机器人可以在网格间移动。
 求机器人可活动的最大范围对应的网格点数目。
说明：
1. 网格左上角坐标为 (0,0)，右下角坐标为 (m−1, n−1)
2. 机器人只能在相邻网格间上下左右移动
输入
第 1 行输入为 M 和 N ，M 表示网格的行数 N 表示网格的列数。
之后 M 行表示网格数值，每行 N 个数值（数值大小用 k 表示），数值间用单个空格分隔，行首行尾无多余空格。
M、N、k 均为整数，且 1 ≤ M, N ≤ 150 ，0 ≤ k ≤ 50
输出
输出 1 行，包含 1 个数字，表示最大活动区域的网格点数目。

示例1：
输入
4 4
1 2 5 2
2 4 4 5
3 5 7 1
4 6 2 4
输出
6
 */

void solve02(vector<vector<int>>&grid)
{
    //可放置于 M × N 的网格 grid 中任意位置
	//每轮重置checked_grid while完以后，记录走过的步数
    //差值小于1 未访问
    int row_size = grid.size();
    int col_size = grid[0].size();

    queue<pair<int, int>>bfs_queue;

    vector<vector<int>>DirectionGrid = {{-1,0},{1,0},{0,-1},{0,1}};

    int result = 0;
    for (int r=0; r<row_size; r++)
    {
        for (int c=0; c<col_size; c++)
        {
            int start_r = r;
            int start_c = c;

            bfs_queue.push(make_pair(start_r, start_c));

            //标记是否访问
            vector<bool>checked_status(col_size, false);
            vector<vector<bool>>checked_grid(row_size, checked_status);
            //标记已访问
            checked_grid[start_r][start_c] = true;

            //当前已访问的步数
            int curr_count = 1;

            while (!bfs_queue.empty())
            {
                pair<int,int>top_node = bfs_queue.front();
                bfs_queue.pop();

                //循环遍历DirectionGrid
                for (auto&dir_vec: DirectionGrid)
                {
                    int next_r = top_node.first + dir_vec[0];
                    int next_c = top_node.second + dir_vec[1];
                    //未越界 差值小于1 未访问
                    bool is_next_r = next_r >= 0 && next_r < row_size;
                    bool is_next_c = next_c >= 0 && next_c < col_size;

                    if (is_next_r&&is_next_c)
                    {
                        int top_value = grid[top_node.first][top_node.second];
                        int next_value = grid[next_r][next_c];
                        bool is_available = abs(top_value - next_value) <= 1;
                        bool is_visited = checked_grid[next_r][next_c];

                        if (is_available && !is_visited)
                        {
                            bfs_queue.push(make_pair(next_r,next_c));
                            //标记已访问
                            checked_grid[next_r][next_c] = true;
                            curr_count += 1;
                        }

                        //------
                    }

                    //forDirectionGrid------
                }


	            //while (!bfs_queue.empty())
            }


            result = max(result, curr_count);
            //for col------
        }

        //for row------
    }



    cout << result;
    //solv02------
}


/*
 0代表平地，山的高度使用1到9来表示，
 小明每次爬山或下山高度只能相差k及k以内，每次只能上下左右一个方向上移动一格，
 小明从左上角(0,0)位置出发

第一行输入m n k(空格分隔)
代表 m*n 的二维山地图，k为小明每次爬山或下山高度差的最大值，然后接下来输入山地图，一共 m行n列，均以空格分隔。
取值范围：
0 < m ≤ 500
0 < n ≤ 500
0 < k < 5

输出描述
请问小明能爬到的最高峰多高，到该最高峰的最短步数，输出以空格分隔。

同高度的山峰输出较短步数。
如果没有可以爬的山峰，则高度和步数都返回0。
备注：所有用例输入均为正确格式，且在取值范围内，考生不需要考虑不合法的输入格式。

示例1
输入
5 4 1
0 1 2 0
1 0 0 0
1 0 1 2
1 3 1 0
0 0 0 9
输出
2 2

根据山地图可知，能爬到的最高峰在(0,2)位置，高度为2，最短路径为(0,0)->(0,1)->(0,2)，最短步数为2。

 */
void solve03(vector<vector<int>>&grid, int limit)
{
    //checked_grid bfs_queue
    //3重条件，未越界，未访问，可到达
    //不断更新最高点的坐标，跟路径，保存while(queue)出来以后，重置路径

    int row_size = grid.size();
    int col_size = grid[0].size();

    vector<bool>checked_status(col_size, false);
    vector<vector<bool>>checked_grid(row_size, checked_status);

    queue<pair<int, int>>bfs_queue;

    //while,for循环遍历方向矩阵
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };

    bfs_queue.push(make_pair(0, 0));
    checked_grid[0][0] = true;

    int max_height = 0, min_step = 0, curr_step = 0;
    while (!bfs_queue.empty())
    {
        int q_size = bfs_queue.size();
        curr_step += 1;
        for (int i=0; i<q_size; i++)
        {
            pair<int,int>top_node = bfs_queue.front();
            bfs_queue.pop();

            for (auto&dir_vec:DirectionGrid)
            {
                int next_r = top_node.first + dir_vec[0];
                int next_c = top_node.second + dir_vec[1];

                bool is_next_r = next_r >= 0 && next_r < row_size;
                bool is_next_c = next_c >= 0 && next_c < col_size;

                if (is_next_r&&is_next_c)
                {
                    bool is_visited = checked_grid[next_r][next_c];
                    int top_value = grid[top_node.first][top_node.second];
                    int next_value = grid[next_r][next_c];
                    bool is_available = abs(top_value - next_value) <= limit;

                    if (!is_visited && is_available)
                    {
                        if (next_value>max_height)
                        {
                            max_height = next_value;
                            min_step = curr_step;
                        }
                        bfs_queue.push(make_pair(next_r,next_c));
                        checked_grid[next_r][next_c] = true;

                        //!is_visited&&is_available
                    }

                    //if (is_next_r&&is_next_c)
                }



                //for DirectionGrid
            }


            //for q_size
        }
        

        //while (!bfs_queue.empty())
    }

    cout << max_height << ' ' << min_step;
    //solve03
}

/*
 5 4 1
0 1 2 0
1 0 0 0
1 0 1 2
1 3 1 0
0 0 0 9
 */


int main()
{
	{
        int row_size, col_size, limit;
        cin >> row_size >> col_size >> limit;
        vector<vector<int>>grid(row_size, vector<int>(col_size));

        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                cin >> grid[r][c];

            }

        }


        //vector<int>vec1 = { 0,1,2,0 };
        //vector<int>vec2 = { 1,0,0,0 };
        //vector<int>vec3 = { 1,0,1,2 };
        //vector<int>vec4 = { 1,3,1,0 };
        //vector<int>vec5 = { 0,0,0,9 };
        //vector<vector<int>>grid = { vec1,vec2,vec3,vec4,vec5 };
        //int limit = 1;
        solve03(grid, limit);

        return 0;
	}


	{
        /*
 4 4
1 2 5 2
2 4 4 5
3 5 7 1
4 6 2 4

2 3
1 3 5
4 1 3
 */
        //vector<int>vec1 = { 1,2,5,2 };
        //vector<int>vec2 = { 2,4,4,5 };
        //vector<int>vec3 = { 3,5,7,1 };
        //vector<int>vec4 = { 4,6,2,4 };
        //vector<int>vec5 = { 1,3,5 };
        //vector<int>vec6 = { 4,1,3 };

        //vector<vector<int>>grid = { vec5, vec6 };
        //solve02(grid);
        int row_size, col_size;
        cin >> row_size >> col_size;
        vector<vector<int>>grid(row_size, vector<int>(col_size));
        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                cin >> grid[r][c];
            }
        }

        solve02(grid);
        return 0;
	}


    /*
 1 0 0
0 1 0
0 0 1

1 1
1 1
 */
    //vector<int>vec1 = { 1,0,0 };
    //vector<int>vec2 = { 0,1,0 };
    //vector<int>vec3 = { 0,0,1 };
    //vector<int>vec4 = {1,1};
    //vector<int>vec5 = {1,1};
    //vector<vector<int>>grid = { vec4,vec5 };
    string input;
    vector<vector<int>>grid;
    while (getline(cin,input))
    {
        if (input.empty()) break;
        stringstream oh_sstream(input);
        string token;
        vector<int>oh_vec;
        while (oh_sstream>>token)
        {
            oh_vec.push_back(stoi(token));
        }
        grid.push_back(oh_vec);
    }

    solve01(grid);

    //main-----
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
